import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/21 10:12
 * @description 贪心 优先使用砖头，但是当砖头没有时只能用梯子，假设当前梯子需要 x, 前面一次砖头为y，
 * 如果y > x, 那么我们肯定希望前面那次使用梯子，这样这次就多了砖头。置换带来正效益
 * 如果 y < x，如果置换，将带来负效益。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] heights = {4,12,2,7,3,18,20,3,19};
        solution.furthestBuilding(heights, 10, 2);
    }
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        int n = heights.length;
        // 前面一次使用砖头数量的最大堆
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        for (int i = 1; i < n; i++) {
            int cnt = heights[i] - heights[i - 1];
            if (cnt > 0) {
                pq.add(cnt);
                // 直接减去
                bricks -= cnt;
                if (bricks < 0) {
                    // 砖头不够
                    if (ladders > 0) {
                        ladders--;
                        bricks += pq.poll();
                    }else {
                        return i-1;
                    }
                }
            }
        }
        return n - 1;
    }
}
